from typing import List


# 77. 组合
# 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
# 你可以按 任何顺序 返回答案。
def combine(n: int, k: int) -> List[List[int]]:
    re = list()
    temp_list = list()

    def back_track(current_n, count_k):
        if count_k == 0:
            re.append(temp_list[:])
            return

        for temp_n in range(current_n, n + 1):
            temp_list.append(temp_n)
            count_k -= 1
            back_track(temp_n + 1, count_k)
            # 进行回溯
            count_k += 1
            temp_list.pop()

    back_track(1, k)

    return re


result = combine(4, 2)
print(f"result:{result}")

result = combine(1, 1)
print(f"result:{result}")

result = combine(5, 2)
print(f"result:{result}")
